package monoqueue;

import java.util.Stack;

/**
 * @author pengfei.hpf
 * @date 2020/3/9
 * @verdion 1.0.0
 * 给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
 *
 * 你找到的子数组应是最短的，请输出它的长度。
 *
 * 示例 1:
 *
 * 输入: [2, 6, 4, 8, 10, 9, 15]
 * 输出: 5
 * 解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
 * 说明 :
 *
 * 输入的数组长度范围在 [1, 10,000]。
 * 输入的数组可能包含重复元素 ，所以升序的意思是<=。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class FindUnsortedSubarray {

    //TODO: 考虑倒序, 正序,重复数据情况.
    public int findUnsortedSubarray(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        int l = nums.length - 1;
        int r = 0;
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < nums.length; i ++){
            while(!stack.isEmpty() && nums[stack.peek()] > nums[i]){
                l = Math.min(l, stack.pop());
            }
            stack.push(i);
        }
        stack.clear();
        for(int i = nums.length - 1; i >= 0; i --){
            while(!stack.isEmpty() && nums[stack.peek()] < nums[i]){
                r = Math.max(r, stack.pop());
            }
            stack.push(i);
        }
        return r > l? r - l + 1: 0;
    }
}
